package Dag

type HeapItem struct {
	score float64
	Path  []string
}

type HeapList []HeapItem

// Len 返回堆中元素的数量
func (h HeapList) Len() int { return len(h) }

// Less 比较两个元素的大小，实现最小堆
func (h HeapList) Less(i, j int) bool {
	return h[i].score < h[j].score
}

// Swap 交换两个元素的位置
func (h HeapList) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
}

// Push 向堆中添加元素
func (h *HeapList) Push(x interface{}) {
	*h = append(*h, x.(HeapItem))
}

// Pop 从堆中移除并返回最后一个元素
func (h *HeapList) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

type PrioritySet struct {
	Capacity int
	Data     *HeapList
}

func PrioritySetInit(capacity int) PrioritySet {
	var list = &HeapList{}

	return PrioritySet{
		Capacity: capacity,
		Data:     list,
	}
}

func (p PrioritySet) Put(item HeapItem) {
	p.Data.Push(item)
	for p.Data.Len() > p.Capacity {
		p.Data.Pop()
	}
}

func (p PrioritySet) Piter() func(yield func(HeapItem) bool) {
	return func(yield func(HeapItem) bool) {
		for i := 0; i < p.Data.Len(); i++ {
			if !yield((*p.Data)[i]) {
				return
			}
		}
	}
}
